package leetcode.part1;

import org.junit.Test;

public class S134 {
    // 从x出发到y，那么从x，y之间的所有地点出发都没法到达终点；所以下次行驶从y之后开始
    public int canCompleteCircuit(int[] gas, int[] cost) {
       int i=0;
       int n=gas.length;

       while (i<n){
           int distance=0;
           int totalGas=0;
           int totalCost=0;
           while (distance<n){
               int j=(i+distance)%n;
               totalCost+=cost[j];
               totalGas+=gas[j];
               if (totalCost>totalGas) break;
               distance++;
           }
           if (distance==n){
               return i;
           }else {
               i=i+distance+1;
           }

       }
       return -1;

    }


    @Test
    public void test() {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        int i = canCompleteCircuit(gas, cost);
        System.out.println(i);
    }
}
